package com.hanxiaozhang.no10leetcode.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一个字符串s，将这个字符串分割成每个子字符串都是回文字符串，返回所有可能的分割方法
 * 实例:
 * 输入: "aab"
 * 输出: [ ["aa","b"], ["a","a","b"] ]
 * <p>
 * 整体思路（灵魂）：
 * -- 每次递归进行一次字符串分割（这里需要用到循环，分割的位置可能是1、2、3...）。然后判断分割子串是否为回文，如果子串是回文将其添加到当前结果集。递归到结束条件时（结果个数等于k时），保存完整结果。
 * -- 每次递归后，需要恢复现场。
 * -- 每次递归分割的字符串是上次分割剩下的子串，即需要记录已经使用过的位置，即start。
 * <p>
 * 具体步骤：
 * 构建一个递归方法：
 * -- 递归入参：需要技巧
 * --- results  结果
 * --- curResult  本次结果
 * --- s         原字符串
 * --- start     每次开始分割位置
 * -- 逻辑：
 * --- 边界条件：start == s.length() 时，加入结果，注意 new ArrayList()
 * --- 循环：开始条件：start，结束条件：i <  s.length()
 * ---- 每次循环 i. 判断子串是否为回文，是回文添加子串，继续进行ii ；ii. 调用 backTrack(...start + 1)； iii.恢复现场
 *
 * @author hanxinghua
 * @create 2024/2/20
 * @since 1.0.0
 */
public class No131PalindromePartitioning {

    public static void main(String[] args) {

        // System.out.println(method_ext("aab"));

        System.out.println(method("aab"));

    }


    public static List<List<String>> method(String s) {
        List<List<String>> results = new ArrayList<>();
        if (s == null) {
            return results;
        }

        backTrack(results, new ArrayList<>(), s, 0);
        return results;
    }

    /**
     * 回溯
     *
     * @param results   结果集
     * @param curResult 本次结果
     * @param s         原字符串
     * @param start     每次开始分割位置
     */
    private static void backTrack(List<List<String>> results, ArrayList<String> curResult, String s, int start) {
        if (start == s.length()) {
            results.add(new ArrayList<>(curResult));
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (judgePalindromeString(start, i, s) && curResult.add(s.substring(start, i + 1))) {
                backTrack(results, curResult, s, i + 1);
                curResult.remove(curResult.size() - 1);
            }
        }
    }


    /**
     * 判断回文
     * <p>
     * Ext：
     * 不用分区奇数回文和偶数回文：
     * 例如奇数回文：abcba 最后一次判断，1与3位置是否相等，即 b == b
     * 例如偶数回文：abba 最后一次判断，1与2位置是否相等，即 b == b
     *
     * @param left  左边界
     * @param right 右边界
     * @param s     字符串
     * @return
     */
    private static boolean judgePalindromeString(int left, int right, String s) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }


    // ==== ====  ==== ====  ==== ====  ==== ====

    /**
     * 给一个字符串s，找出所有是回文的子串。
     *
     * @param str
     * @return
     */
    private static List<String> method_ext(String str) {
        List<String> results = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return results;
        }
        backTrack_ext(results, new StringBuilder(), str.split(""), 0);
        return results;
    }


    private static void backTrack_ext(List<String> results, StringBuilder curResultSb, String[] arr, int index) {

        if (index == arr.length) {
            if (judgePalindromeString(curResultSb)) {
                results.add(curResultSb.toString());
            }
            return;
        }

        backTrack_ext(results, curResultSb, arr, index + 1);
        curResultSb.append(arr[index]);
        backTrack_ext(results, curResultSb, arr, index + 1);
        curResultSb.deleteCharAt(curResultSb.length() - 1);
    }


    /**
     * 判断回文
     *
     * @param sb
     * @return
     */
    private static boolean judgePalindromeString(StringBuilder sb) {
        if (sb.length() == 0) {
            return false;
        }
        if (sb.length() == 1) {
            return true;
        }
        String curResult = sb.toString();
        int L = 0, R = curResult.length() - 1;
        while (L >= 0 && R < curResult.length() && curResult.charAt(L) == curResult.charAt(R)) {
            L--;
            R++;
        }
        if (curResult.length() % 2 == 0) {
            if (R - L == 1) {
                return true;
            }
        } else {
            if (R == L) {
                return true;
            }
        }
        return false;
    }
}
